// 解题思路：
// 判断一棵树是不是平衡二叉树，就需要判断：
// 左子树是不是平衡二叉树
// 右子树是不是平衡二叉树
// 左右子树的高度差是否大于 1
// 判断每个子树的时候又要判断上面的三件事，因此这道题用递归进行求解
// 在解题过程中，我们需要返回左右子树的高度，又要返回左右子数是不是平衡二叉树
// 因此解这道题的技巧就是：
// 如果是平衡二叉树就返回树高，如果不是就返回 -1，表示不是平衡二叉树

public class IsBalancedTree {
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        return dfs(pRoot) != -1;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left);
        if(left == -1) return -1;
        int right = dfs(root.right);
        if(right == -1) return -1;
        if(left - right > 1 || left - right < -1) return -1;

        return Math.max(left, right) + 1;
    }
}

class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  public TreeNode(int val) {
    this.val = val;
  }
}
